package findBestTradeTiming.java;

public class findBestTradeTiming2 {
    public static void main(String[] args) {
        int[] prices = new int[]{7,1,5,3,6,4};
        System.out.println(maxProfit4(prices));

    }

    /**
     * 动态规划
     * @param prices
     * @return
     */
    public static int maxProfit4(int prices[]) {
        if (prices == null || prices.length == 0) return 0;
        int length = prices.length;
        // dp[i][0]代表第i天持有股票的最大收益
        // dp[i][1]代表第i天不持有股票的最大收益
        int[][] dp = new int[length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i-1][0] + prices[i],dp[i-1][1]);
        }
        return dp[length-1][1];
    }

    /**
     * 贪心算法
     * @param prices
     * @return
     */
    public static int maxProfit(int prices[]) {
        int ans = 0;
        int n = prices.length;
        for (int i = 1; i < n; ++i) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }

    /**
     * 快慢指针
     * @param prices
     * @return
     */
    public static int maxProfit3(int prices[]) {
        int p1 = 0;
        int p2 = 1;
        int profit = 0;
        while (p2 < prices.length) {
            if (prices[p1] > prices[p2]) {
                p1 = p2;
                p2 = p2 + 1;
            } else {
                profit = profit + prices[p2] - prices[p1];
                p1 = p2;
                p2 = p2 + 1;
            }
        }
        return profit;
    }

    /**
     * 暴力解法
     * @param prices
     * @return
     */
    public static int maxProfit2(int prices[]) {
        int start = 0;
        int profit = 0;
        while (start < prices.length) {
            int index = getProfit(prices,start);
            if (index > start) {
                profit = profit + prices[index] - prices[start];
                start = index;
            } else {
                start++;
            }
        }
        return profit;
    }

    public static int getProfit(int prices[],int start) {
        int max = prices[start];
        for (int i = start; i < prices.length; i++) {
            if (prices[i] > max) {
                max = prices[i];
                start = i;
            }

            if (max > prices[i]) {
                start = i - 1;
                break;
            }
        }
        return start;
    }
}
